package org.example.two.sort;

import org.example.two.Example;

/**
 * 快速排序
 */
public class QuickAmend01 extends Example {
    @Override
    public void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    public void sort(Comparable[] a, int lo, int hi) {
        if (lo+5 >= hi) {
            for (int i = lo; i <= hi; i++) {
                for (int j = i ; j > lo ; j--) {
                    if(les(a[j],a[j-1])){
                        exch(a,j,j-1);
                    }
                }
            }
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
        Comparable k = a[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            while (les(a[++i], k)) {
                if (i == hi) {
                    break;
                }
            }
            while (les(k, a[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
}
